Article 1114

Title of the article



Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia),
Barsukova Oksana Yur'evna, Senior lecturer, sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia),

Index UDK



Background. In modern mathematics and engineering the theory of synthesis of circuits consisting of unreliable functional elements takes an important place. It should be noted that until now one have used to consider the problems of building reliable circuits, realizing the Boolean functions only. The authors suggest a mathe-matical model for constructing asymptotically optimal reliable circuit, realizing ter-nary logics functions. The researchers studied the problem of realization of ternary logic function circuits of unreliable functional elements in the Rosser – Turkett basis. It is assumed that all the basic elements get faulty independently of each other, and any basic element at any input set (with probability 1–2ε) gives the correct value, and, with ε probability, can give any of the two incorrect values. The aim of this work is to obtain lower and upper bounds for reliability of circuits and to construct asymptotically optimal reliable circuits.
Results. As a result of the study the authors managed to prove the previously obtained upper failure estimates, significantly weakening restrictions (previously the probability depended on n – number of variables, functions, and in this work it was replaced by a constant). The authors proved asymptotic accuracy of the upper bounds, i. e. in the Rosser – Turkett basis they found the K class of ternary logic functions, which means that the lower bound for the unreliability of a circuit is as-ymptotically equal to the upper bound of unreliability for the implementation of any function of this class by any circuit. The K class was explicitly described, as well there was found an estimate for the number of functions, which are included in this class.
Conclusion. It is established that any ternary logic functions can be realized by a circuit that operates with unreliability, asymptotically (at ε → 0), not greater than 6ε. It is proved that the function of K class (containing almost all ternary logic functions) can not be realized by circuits with unreliability, asymptotically (at ε → 0) less than 6ε. Thus almost all ternary logic functions can be realized by asymptotically op-timal reliable circuits that operate with unreliability, that is asymptotically equal to 6ε at ε → 0.

Key words

ternary logics functions, functional elements circuit, unreliability of circuit.

Download PDF

1. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2010, no. 1 (13), pp. 64–79.
2. Grabovskaya S. M. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2011, no. 3 (19), pp. 52–60.
3. Alekhina M. A., Barsukova O. Yu. Izvestiya vysshikh uchebnykh zavedeniy. Povolzh-skiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Phys-ical and mathematical sciences]. 2012, no. 1 (21), pp. 57–65.
4. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Nauka, 1986, 384 p.
5. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, no. 2, p. 59.
6. Alekhina M. A. Fundamenta Informaticae. 2010, no. 104 (3), pp. 219–222.


Дата создания: 18.07.2014 13:17
Дата обновления: 07.07.2015 10:09